//package com.TheEndWork.firstDay;
//
//
//
//import java.util.Scanner;
//
///**
// * @authoer zsj
// * @date 2022/5/23 16:13
// * <p>
// * 二分查找法
// * 给定一个n个元素有序的（升序）整型数组nums 和一个目标值target ，写一个函数搜索nums中的 target，如果目标值存在返回下标，否则返回 -1。
// * leecode 704
// * leecode 278
// * leecode 35
// */
//public class BinaryChop {
//
//    public static void main(String[] args) {
//       /* int[] arr = {-1, 0, 3, 5, 9, 12};
//        int i = methodTwo(arr, 2);
//        System.out.println(i);*/
//        String s = "eabcb";
//        System.out.println(longestPalindrome(s));
//    }
//
//    /**
//     * 暴力枚举
//     */
//    static int methodOne(int[] nums, int target) {
//        for (int i = 0; i < nums.length; i++) {
//            if (nums[i] == target) {
//                return i;
//            }
//        }
//        return -1;
//    }
//
//    /**
//     * 二分查找
//     */
//    static int methodTwo(int[] nums, int target) {
//        int left = 0;//最左边
//        int right = nums.length - 1;//最右边
//        while (left <= right) {
//            int mid = (left + right) / 2;//中间的值
//            if (nums[mid] == target) {
//                return mid;
//            } else
//                //当前值小于目标值，目标值在右边，改变left=mid
//                if (nums[mid] < target) {
//                    left = mid + 1;
//                } else
//                    //当前值大于目标值,在左边,改变right=mid
//                    if (nums[mid] > target) {
//                        right = mid - 1;
//                    }
//        }
//        return -1;
//    }
//
//    /**
//     * 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
//     */
//    public int searchInsert(int[] nums, int target) {
//        if (nums == null) {
//            return -1;
//        }
//        int left = 0;
//        int right = nums.length - 1;
//        while (left < right) {
//            int mid = left + (right - left) / 2;
//            if (nums[mid] == target) {
//                return mid;
//            }
//            //目标值小于中间值，中间的值就等于right就行
//            if (nums[mid] > target) {
//                right = mid - 1;
//            }
//            if (nums[mid] < target) {
//                left = mid + 1;
//            }
//        }
//        return left;
//    }
//
//    /**
//     * todo 错误  需要改，leecode最长回文子串
//     * 给你一个字符串 s，找到 s 中最长的回文子串。
//     */
//    public static String longestPalindrome(String s) {
//        if (s.length() < 2) {
//            return s;
//        }
//        char[] chars = s.toCharArray();
//        int length = chars.length;
//        for (int i = 0; i < length; i++) {
//            for (int j = length - 1; j > i; j--) {
//                if (chars[i] == chars[j]) {
//                    //说明首尾相同
//                    if (isPalindrome(chars, i, j)) {
//                        //记录
//                        return s.substring(i, j);
//                    }
//                }
//            }
//        }
//
//        return s.substring(0, 1);
//    }
//
//    /**
//     * 判断是不是回文串的方法
//     */
//    public static boolean isPalindrome(char[] chars, int left, int right) {
//        while (left < right) {
//            if (chars[left] != chars[right]) {
//                return false;
//            }
//            left++;
//            right--;
//        }
//        return true;
//    }
//
//
//    /**
//     * 上图给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。
//     * 对于每条路径，把路径上面的数加起来可以得到一个和，你的任务就是找到最大的和。
//     * 路径上的每一步只能从一个数走到下一层和它最近的左边的那个数或者右 边的那个数
//     * 此外，向左下走的次数与向右下走的次数相差不能超过 1。
//     * 输入描述
//     * 输入的第一行包含一个整数 N\ (1 \leq N \leq 100)N (1≤N≤100)，表示三角形的行数。
//     * 下面的 N 行给出数字三角形。数字三角形上的数都是 0 至 100 之间的整数。
//     * 思路,其实这道题很简单,找到第一行最大的那个数字，然后判断走左边和右边的那个值更大
//     * 那个更大走哪个,然后result+=那个值,然后又从那个值继续往下判断，直到是最后一行为止
//     *  todo dfs学习完毕回来
//     */
//    public void lanQiao505() {
//        Scanner scanner = new Scanner(System.in);
//        int h = scanner.nextInt();//得到行数
//        int[][] triangle = new int[h][h];
//        for (int i = 0; i < triangle.length; i++) {
//            for (int j = 0; j < h - i; j++) {
//                triangle[i][j] = scanner.nextInt();
//            }
//        }
//
//    }
//
//    /**
//     * 小蓝最近学习了一些排序算法，其中冒泡排序让他印象深刻。
//     * <p>
//     * 在冒泡排序中，每次只能交换相邻的两个元素。
//     * <p>
//     * 小蓝发现，如果对一个字符串中的字符排序，只允许交换相邻的两个字符， 则在所有可能的排序方案中，冒泡排序的总交换次数是最少的。
//     * <p>
//     * 例如，对于字符串 lan排序，只需要 1 次交换。对于字符串 qiao 排序，总共需要 4 次交换。
//     * <p>
//     * 小蓝找到了很多字符串试图排序，他恰巧碰到一个字符串，需要 100 次交 换，可是他忘了吧这个字符串记下来，现在找不到了。
//     * <p>
//     * 请帮助小蓝找一个只包含小写英文字母且没有字母重复出现的字符串，对 该串的字符排序，正好需要 100 次交换。如果可能找到多个，请告诉小蓝最短的那个。如果最短的仍然有多个，请告诉小蓝字典序最小的那个。
//     */
//    public void lanQiao598() {
//        //考虑冒泡排序的复杂度，对于拥有N个字母的字符串，最多需要交换N*(N-1)/2次（完全乱序时）
//        //N*(N-1)/2 = 100 解方程 约等于 15
//        //但是结果等于 105
//        //所以我们将倒序结果的第五位换到第一位就是正确结果
//        System.out.println("abcdefghijklmno");
//        System.out.println("jonmlkihgfedcba");
//    }
//
//    /**
//     * 对于一个字母矩阵，我们称矩阵中的一个递增序列是指在矩阵中找到两个字母，它们在同一行，同一列，或者在同一 4545 度的斜线上，这两个字母从左向右看、或者从上向下看是递增的。
//     * 有LN、LN、AN、AN、IO、AO、LQ、AI、NO、NO、AQ、IN、ANLN、LN、AN、AN、IO、AO、LQ、AI、NO、NO、AQ、IN、AN 等 1313 个 递增序列。注意当两个字母是从左下到右上排列时，从左向右看和从上向下看 是不同的顺序。
//     * 对于下面的 30 行 50 列的矩阵，请问总共有多少个递增序列？
//     */
//    @Test
//    public void lanQiao819() {
//        String s = "VLPWJVVNNZSWFGHSFRBCOIJTPYNEURPIGKQGPSXUGNELGRVZAG\n" +
//                "SDLLOVGRTWEYZKKXNKIRWGZWXWRHKXFASATDWZAPZRNHTNNGQF\n" +
//                "ZGUGXVQDQAEAHOQEADMWWXFBXECKAVIGPTKTTQFWSWPKRPSMGA\n" +
//                "BDGMGYHAOPPRRHKYZCMFZEDELCALTBSWNTAODXYVHQNDASUFRL\n" +
//                "YVYWQZUTEPFSFXLTZBMBQETXGXFUEBHGMJKBPNIHMYOELYZIKH\n" +
//                "ZYZHSLTCGNANNXTUJGBYKUOJMGOGRDPKEUGVHNZJZHDUNRERBU\n" +
//                "XFPTZKTPVQPJEMBHNTUBSMIYEGXNWQSBZMHMDRZZMJPZQTCWLR\n" +
//                "ZNXOKBITTPSHEXWHZXFLWEMPZTBVNKNYSHCIQRIKQHFRAYWOPG\n" +
//                "MHJKFYYBQSDPOVJICWWGGCOZSBGLSOXOFDAADZYEOBKDDTMQPA\n" +
//                "VIDPIGELBYMEVQLASLQRUKMXSEWGHRSFVXOMHSJWWXHIBCGVIF\n" +
//                "GWRFRFLHAMYWYZOIQODBIHHRIIMWJWJGYPFAHZZWJKRGOISUJC\n" +
//                "EKQKKPNEYCBWOQHTYFHHQZRLFNDOVXTWASSQWXKBIVTKTUIASK\n" +
//                "PEKNJFIVBKOZUEPPHIWLUBFUDWPIDRJKAZVJKPBRHCRMGNMFWW\n" +
//                "CGZAXHXPDELTACGUWBXWNNZNDQYYCIQRJCULIEBQBLLMJEUSZP\n" +
//                "RWHHQMBIJWTQPUFNAESPZHAQARNIDUCRYQAZMNVRVZUJOZUDGS\n" +
//                "PFGAYBDEECHUXFUZIKAXYDFWJNSAOPJYWUIEJSCORRBVQHCHMR\n" +
//                "JNVIPVEMQSHCCAXMWEFSYIGFPIXNIDXOTXTNBCHSHUZGKXFECL\n" +
//                "YZBAIIOTWLREPZISBGJLQDALKZUKEQMKLDIPXJEPENEIPWFDLP\n" +
//                "HBQKWJFLSEXVILKYPNSWUZLDCRTAYUUPEITQJEITZRQMMAQNLN\n" +
//                "DQDJGOWMBFKAIGWEAJOISPFPLULIWVVALLIIHBGEZLGRHRCKGF\n" +
//                "LXYPCVPNUKSWCCGXEYTEBAWRLWDWNHHNNNWQNIIBUCGUJYMRYW\n" +
//                "CZDKISKUSBPFHVGSAVJBDMNPSDKFRXVVPLVAQUGVUJEXSZFGFQ\n" +
//                "IYIJGISUANRAXTGQLAVFMQTICKQAHLEBGHAVOVVPEXIMLFWIYI\n" +
//                "ZIIFSOPCMAWCBPKWZBUQPQLGSNIBFADUUJJHPAIUVVNWNWKDZB\n" +
//                "HGTEEIISFGIUEUOWXVTPJDVACYQYFQUCXOXOSSMXLZDQESHXKP\n" +
//                "FEBZHJAGIFGXSMRDKGONGELOALLSYDVILRWAPXXBPOOSWZNEAS\n" +
//                "VJGMAOFLGYIFLJTEKDNIWHJAABCASFMAKIENSYIZZSLRSUIPCJ\n" +
//                "BMQGMPDRCPGWKTPLOTAINXZAAJWCPUJHPOUYWNWHZAKCDMZDSR\n" +
//                "RRARTVHZYYCEDXJQNQAINQVDJCZCZLCQWQQIKUYMYMOVMNCBVY\n" +
//                "ABTCRRUXVGYLZILFLOFYVWFFBZNFWDZOADRDCLIRFKBFBHMAXX";
//        char[][] arr = new char[30][50];
//        int beginIndex = 0;
//        int endIndex = 50;
//        int temp = 0;
//        for (int i = 0; i < 30; i++) {
//            for (int j = 0; j < endIndex; j++) {
//                arr[i][j] = s.charAt(temp++);
//            }
//        }
//
//
//    }
//
//
//}
